package Aula16;

public class MinHeapImpl implements MinHeap {

	private int[] vetor;

	public int construirHeap(int[] vetorNumerosDesordenado) {
		if (vetorNumerosDesordenado != null
				&& vetorNumerosDesordenado.length > 0) {
			vetor = new int[vetorNumerosDesordenado.length + 1];
			for (int i = 1; i < vetor.length; i++) {
				vetor[i] = vetorNumerosDesordenado[i - 1];
			}
			for (int i = vetor.length / 2; i > 0; i--) {
				minHeapify(i);
			}
			return 1;
		}
		return 0;
	}

	public int extrairMinimo() {
		if (vetor != null) {
			int smaller = vetor[1];
			int[] novoVetor = new int[vetor.length - 1];
			novoVetor[1] = vetor[novoVetor.length];
			for (int i = 2; i < novoVetor.length; i++) {
				novoVetor[i] = vetor[i];
			}
			vetor = novoVetor;
			minHeapify(1);
			return smaller;
		}
		return 0;
	}

	public int getMinimo() {
		if (vetor == null) {
			return 0;
		}
		return vetor[1];
	}

	public void inserirChave(int novaChave) {
		if (vetor != null) {
			int[] novoVetor = new int[vetor.length + 1];
			for (int i = 1; i < vetor.length; i++) {
				novoVetor[i] = vetor[i];
			}
			vetor = novoVetor;
			int i = vetor.length - 1;
			while (i > 1 && vetor[i / 2] > novaChave) {
				vetor[i] = vetor[i / 2];
				i = i / 2;
				vetor[i] = novaChave;
			}
		}
	}

	public void minHeapify(int i) {
		if (vetor != null) {
			int l = 2 * i;
			int r = 2 * i + 1;
			int smaller;
			if (l < vetor.length && vetor[l] < vetor[i]) {
				smaller = l;
			} else {
				smaller = i;
			}
			if (r < vetor.length && vetor[r] < vetor[smaller]) {
				smaller = r;
			}
			if (i != smaller) {
				int aux = vetor[i];
				vetor[i] = vetor[smaller];
				vetor[smaller] = aux;
				minHeapify(smaller);
			}
		}
	}

	public static void main(String[] args) {
		MinHeap h = new MinHeapImpl();

		int[] vetor = { 3, 5, 1, 2, 9, -4 };

		if (h.construirHeap(vetor) == 1) {
			System.out.println(h.extrairMinimo());
			System.out.println(h.getMinimo());
			h.inserirChave(-10);
			System.out.println(h.getMinimo());
		}
	}
}
